/**
 * https://leetcode.cn/submissions/detail/560012525/
 * 2009. 使数组连续的最少操作数
 * hard 黄伟杰 2024.8.31
 * 滑动窗口
 */

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int minOperations(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int m = unique(nums.begin(), nums.end()) - nums.begin(); // 去重
        int ans = 0, left = 0;
        // ans 表示有几个数不用被修改
        // left 指向的是数组的最小值，所以最大值为nums[left]+n-1
        for (int i = 0; i < m; i++)
        {
            while (nums[left] < nums[i] - n + 1) // 每个数都与最小的比较
                left++;                          // 增加最小值,增加要修改的数
            // 假如数组是2,4,6,8
            // 到4时,left的指到4,2就要修改
            // 到6时,left会指到6,4和6都要修改,但是一个数如何修改,只会用一次修改操作
            ans = max(ans, i - left + 1); // 更新不用修改的次数
        }

        return n - ans;
    }
};